This invention relates to packet-based asynchronous networks, and in particular to a circuit emulation service (CES) therefor.
Packet switching offers several performance advantages over circuit switching, particularly with regard to efficient utilization of available bandwidth. Recent advances in Constant Bit Rate services have enabled speech to be transmitted over switched virtual circuits through a packet-based network. CES offers backward compatibility between existing circuit-switched telephony services and asynchronous transfer mode (ATM) technology.
Meeting the quality of service requirements of CES is not a trivial task. The cell delay variation (CDV) between successive cells of a connection has to be minimized to reduce the size of the play-out buffer at the receiver end, while the cell transfer delay (CTD) has to be constrained to be no larger than the delay in the circuit-switched
CES cells (or, in general, CBR or Constant Bit Rate cells) are generated at regular intervals. Ideally CES cells from the same connection should follow each other through the switch at regular intervals as if according to a virtual clock. However clock wander is ubiquitous, so an asynchronous CES connection can have an effective cell assembly rate different from the nominal assembly rate and this effective assembly rate is usually unknown to the scheduler. This means the virtual clock for each connection may be either fast or slow. This introduces CDV at the ATM network access point.
Another main cause of CDV is the cell contention caused by simultaneous arrivals at ATM multiplexing points. This adds extra CDV across the ATM network.
Unless the CDV is absorbed in an upstream shaping buffer (at the cost of increasing the CTD), the downstream node will perceive additional jitter.
Currently, some simple cell scheduling algorithms, such as First-In-First-Out (FIFO) and round-robin are used in the ATM networks, but they do not optimize CDV performance. One algorithm, the Earliest-Deadline-First (EDF) service discipline, has been proposed to reduce CDV for the packet voice services, see T. Chen, J. Wairand, and D. Messerschmitt, Dynamic Priority Protocols for Packet Voice. IEEE Journal on Selected Areas in Communications, Vol. 7, No.5, pp. 632-643, June 1989.
EDF can minimize the CDV if a cell""s deadline can be accurately calculated. However, since the deadline for each connection is determined by the unknown connection time clock (time stamps in ATM cells to carry a play-out deadline are not practical), EDF is not applicable.
U.S. Pat. No. 5,515,363 discloses a technique for determining the lateness of the head-of-the-line cell and assigning priority for transmission to the latest cell in an asynchronous network providing a CES service. A similar technique is disclosed in PROCEEDINGS OF THE IEEE CONFERENCE ON COMPUTER COMMUNICATIONS 1966 (INFOCOM ""96), vol. 2, Mar. 24, 1966, San Francisco, US; pages 647-654 (VISHNU et al.). This technique is designed to guarantee a minimum specified bandwidth to each backlogged virtual connection
IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE 1995 (GLOBECOM ""95), VOL.2, Nov. 14, 1995, Singapore; pages 1064-1070 (PANCHA et al.) discloses a technique for minimizing delay in packet switched networks.
Such techniques, however, are not able to adapt to slow drift in the virtual clock or take into account cell jitter, which is inevitably present in an ATM network.
According to the present invention there is provided a method of scheduling cells received at a queueing module provided for each connection into an asynchronous network for a circuit emulation service CES, comprising establishing the virtual clock of each connection by on-line traffic measurement in real time, estimating the lateness of the head-of-the-line cell for each queue relative to a deadline for departure of that cell determined by the established virtual clock by means of a moving window filter able to adapt to the slow drift in the virtual clock and at the same time smooth the variations caused by jitter due to cell contention, and giving the highest priority for transmission to the cell having the largest lateness value.
By attempting to match connection cell departures to a virtual clock, the above method overcomes both of the root causes for CDV and optimizes the CDV performance for ATM CES.
The above scheme has little computational overhead and requires only a few memory locations per CES stream. It can be implemented in a traffic shaper with minimum extra hardware requirements, or in a Segmentation And Reassemble (SAR) device for ATM CES. A simulator of VFS has been built and tested under realistic traffic conditions. VFS consistently out-perform the FIFO discipline under both transient and steady traffic conditions.
The invention thus proposes to estimate cell lateness relative to a deadline established by a virtual clock associated with each connection. The estimate is based on real-time measurements. This estimate is fed into the EDF scheduler which identifies the latest cell which gets highest priority for transmission.
The invention also provides a device for scheduling cells into an asynchronous network for providing a circuit emulation service CES, comprising a queueing module for each connection receiving incoming cells, a relative lateness estimator connected to said queueing module for estimating the relative lateness on a per connection basis of the head-of-the-line cell for each queue relative to a deadline for departure of that cell determined by a virtual clock established for that connection by means of a moving window filter able to adapt to the slow drift in the virtual clock and at the same time smooth the variations caused by jitter due to cell contention, and an earliest deadline first unit connected to said lateness estimator for transmitting outgoing cells and giving highest priority to the cell having the largest lateness value.
The invention will now be described in more detail, by way of example, only with reference to the accompanying drawings, in which:
FIG. 1 depicts the high level structure of the Variation Fluctuation Smooth(VFS) scheme;
FIG. 2 shows the arrival times of DS1 cells;
FIG. 3 shows a comparison of transient behaviour between VFS and FIFO schemes (synchronized phase); and
FIG. 4 shows a comparison of transient behaviour between VFS and FIFO schemes (random phase);